In many data processor applications, several devices may occasionally request the exclusive use of a single shared resource. The most common single shared resource in the field of digital computing systems is a shared communications bus. For example, a communications bus may interconnect a data processor, a memory subsystem, a video graphics driver subsystem and various input/output ("I/O") subsystems. Each of these devices may occasionally need to exclusively use the communications bus to transfer data between devices. Also, two or more of these devices may occasionally need to exclusively use the communications bus at the same time.
A resource arbitrator is a device that resolves simultaneous requests for a single resource according to a resource arbitration protocol. A resource arbitration protocol is a set of rules that specifies which resource user is granted the exclusive use of a particular resource given all possible combinations of requests for the resource. Therefore, a bus arbitrator resolves simultaneous requests for a single communications bus according to a bus arbitration protocol.
Arbitration protocols, in general, and bus arbitration protocols, in particular, are designed in light of two criteria. First, resource use should be maximized. This metric is commonly referred to as resource bandwidth. Second, no device requesting use of the resource (a "requester") should ever be permanently excluded from using the resource. Ideally, each requester should have use of the resource as often as every other requester of similar importance. This criteria is often referred to as "fairness."
The dual criteria of bandwidth and fairness are often competing design goals. For instance, high resource bandwidth implies a high resource operating rate and thus a fast arbitrator. Unfortunately, a fast arbitrator must follow a simple resource arbitration protocol that is generally not entirely "fair." Conversely, a completely fair arbitrator implies a more complicated arbitration protocol and a slower arbitrator. A slower arbitrator may limit the operating rate of the resource or may occasionally forgo resource use entirely to maintain fairness. In either case, resource bandwidth is not maximized.